//
// Created by Win10 on 2023/4/18.
//

#include "binary_search.h"

// 只需要查找有无，不需要区分左右边界
int BinarySearch(const int arr[] ,int length, int target){
  int left = 0, right = length-1;
  while(left <= right){
    // 等同于(left+right)/2，但是当left和right较大时两者相加容易发生溢出
    int mid = left + (right-left) / 2;
    // 找到了target就直接返回mid
    if(arr[mid] == target)    return mid;
      // 如果当前值大于target，而数组是升序的，说明target在数组的左半边[left,mid-1]，但是由于区间定义是左闭右开，因此数组左半边写成[left,mid)，所以right=mid
    else if(arr[mid] > target)    right = mid+1;
      // 最后，如果当前值小于target，则说明target在数组的右半边[mid+1,right)，因此left直接等于mid+1就好了
    else left = mid + 1;
  }
  // 找不到就返回-1
  return -1;
}

// 下边界，也就是数组中第一次出现target的位置
int BinarySearchLowwer(const int arr[] ,int length, int target){
  int left = 0,right = length-1,ret = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] >= target) {
      // 中间的值要是大于target肯定往左区间找，如果中间值等于target呢
      // 因为我们是找下边界，所以也是往左区间搜索，因此这两种情况可以合并
      // 中间值大于等于target都往左区间[left,mid-1]查找
      ret = mid;  // pos会被不断的往左更新，直到为下边界
      right = mid - 1;
    }
    else {
      // 这个简单，中间的数小于target，往右子区间[mid+1,right]查找
      left = mid + 1;
    }
  }
  return ret;
}

// 上边界，也就是数组中最后一次出现target的位置
int binarySearchUpper(const int arr[] ,int length, int target) {
  int left = 0, right = length - 1, ret = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] > target) {
      // 中间的值要是大于target肯定往左区间找，如果中间值等于target呢
      // 因为我们是找上边界，所以肯定往又区间找，所以放到else情况里面
      right = mid - 1;
    } else {
      // 中间的数小于等于target，往右子区间[mid+1,right]查找
      ret = mid;  // pos会被不断的往左更新，直到为下边界
      left = mid + 1;
    }
  }
  return ret;
}